//
//  BinaryTreeNode.m
//  Test
//
//  Created by aReu on 2017/3/20.
//  Copyright © 2017年 CBswift. All rights reserved.
/*
    http://www.tuicool.com/articles/z2QJzub
    每天一练习
 */

#import "TreeNode.h"

@implementation TreeNode


//20170320
+ (TreeNode *)returnTreeNode:(NSArray<NSString*>*)arr {
    TreeNode *node = nil;
    for (NSString *value in arr){
        node = [self creatNode:value.integerValue Node:node];
    }
    return node;
}

+ (TreeNode*)creatNode:(NSInteger)value Node:(TreeNode*)node {
    if (!node) {
        node = [TreeNode new];
        node.value = value;
        return node;
    }
    if (value <= node.value) {
       node.leftNode = [self creatNode:value Node:node.leftNode];
    }else {
       node.rightNode = [self creatNode:value Node:node.rightNode];
    }
    return node;
}

//搜索根节点  0322
+ (TreeNode *)treeNodeAtIndex:(NSInteger)index inTree:(TreeNode *)rootNode {
    //按层次遍历
    if (!rootNode || index < 0) {
        return nil;
    }
    NSMutableArray *queueArray = [NSMutableArray array]; //数组当成队列
    [queueArray addObject:rootNode]; //压入根节点
    while (queueArray.count > 0) {
        TreeNode *node = [queueArray firstObject];
        if (index == 0) {
            return node;
        }
        [queueArray removeObjectAtIndex:0]; //弹出最前面的节点，仿照队列先进先出原则
        index--; //移除节点，index减少
        if (node.leftNode) {
            [queueArray addObject:node.leftNode]; //压入左节点
        }
        if (node.rightNode) {
            [queueArray addObject:node.rightNode]; //压入右节点
        }
    }
    //层次遍历完，仍然没有找到位置，返回nil
    return nil;
}

@end
